package search;

import sort.quick.QuickSort;
import util.Util;

public class BinSearch {

    public static void main(String[] args) {
        int[] arr = new int[]{0, 3, 3, 3, 9, 9, 6, 7, 9, 9, 3};
        QuickSort.quickSort(arr);

        Util.print(arr);

        int index = search(arr, 4);
        System.out.println(index);

        index = binSearch(arr, 4);
        System.out.println(index);

    }

    public static int search(int[] table, int value) {
        if (null == table || table.length == 0) {
            return -1;
        }

        if (table.length == 1) {
            if (table[0] == value) {
                return 0;
            }
            return -1;
        }
        return binSearch(table, 0, table.length - 1, value);
    }

    private static int binSearch(int[] table, int low, int high, int value) {
        if (low > high) {
            return -1;
        }
        int mid = low + high >>> 1;
        int a = table[mid];
        if (value > a) {
            low = mid + 1;
            return binSearch(table, low, high, value);
        } else if (value < a) {
            high = mid - 1;
            return binSearch(table, low, high, value);
        } else {
            int index = mid;
            while (true) {
                if (value == table[mid - 1]) {
                    index = mid - 1;
                }
                break;
            }
            return index;
        }
    }

    private static int binSearch(int[] table, int value) {
        if (null == table || table.length == 0) {
            return -1;
        }

        if (table.length == 1) {
            if (table[0] == value) {
                return 0;
            }
            return -1;
        }

        for (int low = 0, high = table.length - 1; ; ) {

            if (low>high) {
                return -1;
            }

            int mid = low + high >>> 1;
            int a = table[mid];
            if (value > a) {
                low = mid + 1;
            } else if (value < a) {
                high = mid - 1;
            } else if (value == a) {
                int index = mid;
                while (true) {
                    if (value == table[mid - 1]) {
                        index = mid - 1;
                    }
                    break;
                }
                return index;
            } else {
                return -1;
            }
        }
    }


}
